package com.mlh.violent;

public class NQueens {
	//N皇后的解法只有一种 暴力递归  尝试所有可能
	//常数时间可以优化  利用位运算

	//返回一共有多少种解法
	public static int num1(int n){
		//传入n  n=1 or n>=4  此时问题才是有解的
		if(n!=1&&n<4){
			return 0;
		}
		int[] record=new int[n]; //这个数组存储了皇后的位置  索引为行  值为列  因为要满足规则 皇后只能分别在每一行  因此用索引代替
		return process(record,n,0);
	}

	public static int process(int[] record, int n, int row) {
		if (row == n) {//如果row到达到n时，说明0到n-1已经拍好了  算一种解法了 退出  实际上这就是递归头 即何时退出递归
			return 1;
		}
		int res=0;
		for (int j = 0; j < n; j++) {
			if (isValid(row,j,record)) {
				record[row] = j;
				res+=process(record, n, row + 1);
			}
		}
		return res;
	}

	//该方法用于判断该棋子的位置是否符合规则 不在同一行 同一列 同一斜线
	public static boolean isValid(int row,int column,int[]record){
		for(int i=0;i<row;i++){
			if(record[i]==column){//看看是否和前面的棋子同一列
				return false;
			}
			if(Math.abs(row-i)==Math.abs(record[i]-column)){
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		int n = 14;
		long start = System.currentTimeMillis();
		System.out.println(num1(n));
		long end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");



	}
}
